#ifndef __PATH_H__
#define __PATH_H__

#include "dynamic-tree.h"
#include <string>

using namespace std;

namespace Trees
{
	template <class V, class E> class Path;
	
	template <class V, class E>
	class DynamicPathTree : public DynamicTree<V,E>
	{
	public:
		DynamicPathTree(const V& val);
		virtual ~DynamicPathTree() {};
	
		virtual DynamicTree<V,E>* Parent() const;
		virtual DynamicTree<V,E>* Root() const;
		virtual const E Cost() const;
		virtual DynamicTree<V,E>* MinCost() const;
		virtual void Update(const E& x);
		virtual void Link(DynamicTree<V,E>* otherRoot, const E& x);
		virtual const E Cut();
		virtual void Evert();

		virtual Path<V,E>* GetPath() const = 0;
		virtual DynamicPathTree<V,E>* Before() const = 0;
		virtual DynamicPathTree<V,E>* After() const = 0;
		virtual const E PCost() const = 0;
		virtual Path<V,E>* Expose(const string& logPrefix = "") const = 0;
		virtual void Split(Path<V,E>** p, Path<V,E>** q, E* x, E* y, const string& logPrefix = "") = 0;
		
		virtual const E DCost() const { return m_dCost; }
		virtual DynamicPathTree<V,E>* DParent() const { return m_dParent; }
		
		DynamicPathTree<V,E>* m_dParent;
		E m_dCost;
	};

	template <class V, class E>
	class Path
	{
	public:
		virtual ~Path() {};
	
		virtual DynamicPathTree<V,E>* Head() const = 0;
		virtual DynamicPathTree<V,E>* Tail() const = 0;
		virtual DynamicPathTree<V,E>* PMinCost() const = 0;
		virtual void PUpdate(const E& x) = 0;
		virtual void Reverse() = 0;
		virtual Path<V,E>* Concatenate(Path<V,E>* tail, const E& x) = 0;
		
		virtual Path<V,E>* Splice() = 0;

	};
}

#endif
